package LinkedList;

public class _86_PatritionList {
    public ListNode partition(ListNode head, int x) {
        if(head==null) return null;
        ListNode p = head;
        ListNode lessNode = new ListNode(Integer.MIN_VALUE);
        ListNode moreNode = new ListNode(Integer.MIN_VALUE);
        ListNode lNode = lessNode;
        ListNode mNode = moreNode;
        while(p!=null){
            ListNode tempNode = new ListNode(Integer.MIN_VALUE);
            tempNode.val = p.val;
            if(p.val<x){
                tempNode.val = p.val;
                lNode.next = tempNode;
                lNode = lNode.next;
            }else{
                tempNode.val = p.val;
                mNode.next = tempNode;
                mNode = mNode.next;
            }
            p = p.next;
        }
        if(moreNode.next!=null){
            lNode.next = moreNode.next;
        }
        return lessNode.next;
    }
}
